package Algorithm.search;

/**
 * 在一个非递减数组中寻找target的插入位置，若存在相同元素则插入到它们后面
 */
public class SearchInsert2 {

    /**
     * 思路：即寻找第一个大于target的元素的位置，将循环不变量[0, low）设定为小于等于target的元素
     * (high, length-1]为大于target的元素，则循环结束后low指向的元素即为第一个大于target的元素
     */
    public int searchInsert2(int[] nums, int target) {
        int low = 0, high = nums.length - 1;
        while (low <= high) {
            int mid = (low + high) / 2;
            //当nums[mid]小于等于target时，向右移动low
            if (nums[mid] <= target) low = mid + 1;
            else high = mid - 1;
        }
        return low;
    }
}
